﻿/**************************************************************
 * Copyright Eastmoney Corporation. All rights reserved.
 * 
 * Author: guitao(guitao@eastmoney.com) 
 * Create Date: 2020/7/23 16:23:19
 * Description:
 *          
 * Revision History:
 *      Date         Author               Description
 *              
***************************************************************/

using System;
using System.Collections.Generic;
using System.Text;
using Xunit;

namespace Algorithm.Samples
{
    public class ListNodeAlgorithmsTest
    {
        private ListNodeAlgorithms _listNodeAlgorithms;

        public ListNodeAlgorithmsTest()
        {
            _listNodeAlgorithms = new ListNodeAlgorithms();
        }

        [Theory(DisplayName = "获取两个链表相交的起始节点")]
        [MemberData(nameof(ListNodeMemberData.InersectionNode_TestData), MemberType = typeof(ListNodeMemberData))]
        public void Should_GetInersectionNode(ListNode headA, ListNode headB, ListNode expectListNode)
        {
            var array1 = new int[] { 1, 2, 3, 4 };
            var array2 = new int[] { 1, 2, 3, 4 };
            Assert.Equal(array1, array2);

            var actualListNode = _listNodeAlgorithms.GetInersectionNode(headA, headB);

            Assert.Equal(expectListNode, actualListNode);
        }

        [Fact]
        public void Should_RecordNode()
        {
            var node = ConvertToListNode(new int[] { 1, 2, 3, 4 });
            _listNodeAlgorithms.ReorderList(node);
            var newList = ConvertTolArray(node);
            Assert.Equal(1, newList[0]);
            Assert.Equal(4, newList[1]);
            Assert.Equal(2, newList[2]);
            Assert.Equal(3, newList[3]);
        }


        private ListNode ConvertToListNode(int[] array)
        {
            if (array == null) return null;
            ListNode n = new ListNode(-1);
            ListNode temp = n;
            for (int i = 0; i < array.Length; i++)
            {
                temp.next = new ListNode(array[i]);
                temp = temp.next;
            }
            return n.next;
        }
        private int[] ConvertTolArray(ListNode head)
        {
            if (head == null) return null;
            var list = new List<int>();
            ListNode temp = head;
            while (temp != null)
            {
                list.Add(temp.val);
                temp = temp.next;
            }
            return list.ToArray();
        }
    }

    public class ListNodeMemberData
    {
        private static ListNode CommonListNode1 = new ListNode(8) { next = new ListNode(4) { next = new ListNode(5) } };
        private static ListNode CommonListNode2 = new ListNode(2) { next = new ListNode(4) };
        private static readonly List<object[]> Data_InersectionNode = new List<object[]>
        {
            new object[]{
                new ListNode(4) { next=new ListNode(1) { next=CommonListNode1} },
                new ListNode(5) { next=new ListNode(0) { next=new ListNode(1) { next=CommonListNode1} } },
                CommonListNode1
            },
            new object[]{
                new ListNode(0){ next=new ListNode(9){ next=new ListNode(1){ next=CommonListNode2} } },
                new ListNode(3){ next=CommonListNode2},
                CommonListNode2
            },
            new object[]{
                new ListNode(2){ next=new ListNode(6){ next=new ListNode(4)} },
                new ListNode(1){ next=new ListNode(5)},
                null
            }
        };
        private static readonly List<object[]> Data_ReorderNode = new List<object[]>
        {
             new object[]{
                new int[]{ 1,2,3,4 },
                new int[]{ 1,4,2,3}
            },
            new object[]{
                new int[]{ 1,2,3,4,5 },
                new int[]{ 1,5,2,4,3}
            },
        };









        public static IEnumerable<object[]> InersectionNode_TestData => Data_InersectionNode;
        public static IEnumerable<object[]> ReorderNode_TestData => Data_ReorderNode;
    }

    public class ListNodeAlgorithms
    {
        /// <summary>
        /// 获取A、B两个链表相交的起始节点
        /// 我们需要做的事情是，让两个链表从同距离末尾同等距离的位置开始遍历。这个位置只能是较短链表的头结点位置。
        /// 为此，我们必须消除两个链表的长度差 
        /// 指针 pA 指向 A 链表，指针 pB 指向 B 链表，依次往后遍历
        /// 如果 pA 到了末尾，则 pA = headB 继续遍历
        /// 如果 pB 到了末尾，则 pB = headA 继续遍历
        /// 比较长的链表指针指向较短链表head时，长度差就消除了
        /// 如此，只需要将最短链表遍历两次即可找到位置
        /// </summary>
        public ListNode GetInersectionNode(ListNode headA, ListNode headB)
        {
            if (headA == headB) return headA;
            if (headA == null || headB == null) return headB;

            ListNode pa = headA;
            ListNode pb = headB;

            //地址相同
            while (pa != pb)
            {
                pa = pa == null ? headB : pa.next;
                pb = pb == null ? headA : pb.next;
            }
            return pa;
        }

        /// <summary>
        /// 重排链表
        /// 给定一个单链表 L：L0→L1→…→Ln-1→Ln ，将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…
        /// 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
        /// </summary>
        /// <param name="head"></param>
        /// <returns></returns>
        public void ReorderList(ListNode head)
        {
            List<ListNode> list = new List<ListNode>();
            ListNode temp = head;
            while (temp != null)
            {
                list.Add(temp);
                temp = temp.next;
            }
            var array = list.ToArray();
            int m = 0;
            int n = array.Length - 1;


            ListNode newNode = new ListNode(-1);
            var temp2 = newNode;
            while (m < n)
            {
                temp2.next = array[m];
                temp2 = temp2.next;
                m++;

                temp2.next = array[n];
                temp2 = temp2.next;
                n--;
            }
            if (m == n)
            {
                temp2.next = array[m];
                temp2 = temp2.next;
            }
            temp2.next = null;
            head = newNode.next;

        }
    }


    /// <summary>
    /// 链表结构
    /// </summary>
    public class ListNode
    {
        public int val;
        public ListNode next;
        public ListNode(int x) { val = x; }
    }
}
